AdaBoost(Adaptive Boosting)

이전 model이 틀렸던 training data가 포함될 확률이 높게 하여 random하게 dataset을 구성해 학습시키는 Boosting의 일종.

$p_{l}^{t}$ : sample $(x^{t}, r^{t})$ 가 model $h_{l}$ 을 학습하기 위한 데이터로 구성될 확률.

error rate가 $\frac{1}{2}$ 보다 작기만 하면 사용하는, weak learner를 사용한다. 이는 Decision Tree에 대해 모든 tree를 키우지 않고, 어느 정도만 키워 사용하는 decision stump를 사용할 수도 있다.

algorithm

$p_{l}^{t} = \frac{1}{N}$ 으로 동일하게 initializaiton.
base learner $h_{l}$ 에 대해 $p_{l}^{t}$ 를 기반으로 추출한 Random Sample dataset에 대해 학습한다.
error rate: $ϵ_{l} = t \sum 1 (h_{l} (x^{t}) \neq = r^{t}) p_{l}^{t}$
만약 error rate가 $\frac{1}{2}$ 보다 크다면 $L = l - 1$ : 해당 base-leaner는 성능이 좋지 않으므로 해당 base-learer를 제외하고 종료한다.
그렇지 않다면, 만약 $h_{l}$ 이 잘 맞추는 $x^{t}$ 에 대해서는 , $p_{l + 1}^{t} = \frac{ϵ _{l}}{1 - ϵ _{l}} p_{l}^{t}$ . error rate가 $\frac{1}{2}$ 보다 크므로 다음 base learner $h_{l + 1}$ 이 해당 데이터에 대해 학습할 확률이 올라간다.
만약 잘 맞추지 못하는 데이터 $x^{t}$ 에 대해서는 $p_{l + 1}^{t} = p_{l}^{t}$ .
$p_{l + 1}^{t} = \frac{p _{l + 1}^{t}}{t \sum p _{l + 1}^{t}} for all l$ : 확률의 총합이 1이 되도록 scaling한다.
이러한 과정을, $1$ 번째 base-learner부터, $L$ 번째 base-learer까지 반복한다.

Voting 방식을 이용한다.

y = l \sum (lo g \frac{1 - ϵ _{l}}{ϵ _{l}} h_{l})

error rate( $ϵ_{l}$ )이 작으면 작을 수록 weight가 커지는 일종의 weighted sum.